Traffic engineering (TE) tools are used in modern telecommunication networks for calculating connections carrying user traffic, in order to balance the traffic load on the various segments of the connections and on the various network elements (routers, switches), so that none of these segments and network elements are over-utilized or under-utilized. This aim is achieved carrying user traffic over the connection calculated by the TE tool, crossing specific network elements; this connection is usually defined “intended” (or “nominal”) connection.
In this scenario, in case of a failure on a segment of the intended connection, a backup connection is calculated and activated for protecting the traffic over the intended connection, that is the user traffic is rerouted from the intended to the backup connection. The backup connection can be pre-calculated (and this process is usually defined “protection”) or calculated run-time (and it is usually defined “restoration”). In the first case the backup connection is calculated or assigned before the failure occurs and, if calculated, it is stored; it can be fully disjoint from the intended connection, that is intended and backup connections don't have common segments, or can be partially disjoint, that is intended and backup connections have at least one common segment. In case of fully disjoint backup connections, one backup connection is usually pre-calculated, because it can protect the intended connection after a failure of any segment of the intended connection, while in case of partially disjoint backup connections, for each possible failure on a segment is required one (or at least one) pre-calculated backup connection. On the contrary, in restoration the backup connection is calculated run-time, that is after the failure occurs. The advantage of protection compared to restoration is usually a smaller recovery time, while the disadvantage is to require more network resources (for example some segments are assigned in advance and are used only for protection or available segments are required for the disjoint backup connection).
When the failure clears, in traffic engineered networks the traffic is always reverted from the backup to the intended connection, in order to carry the user traffic over the intended connection calculated by the TE tool. Moreover, the reversion is required because in case of a further failure on the backup connection, the calculation of a further backup connection is more complex and this calculation could fail.
In traditional networks the calculation of the backup connection can be performed by a centralized network manager controlling network elements and controlling connections (intended and backup) crossing the network elements; the centralized manager is a software application running on a management station and performing network management functions and it is responsible for configuration of the connections, monitoring alarms and performance of the connections, for protecting the intended connections providing a backup connection in case of a failure on a segment of the intended connection. In order to perform these functions, it stores into a MIB (Management Information Base) the list of identifiers of the intended connections within the controlled domain and for each intended connection the source and destination network elements and the list of the intermediate network elements (or the list of segments, identified by two network elements). In a traffic engineered network including a protection mechanism, the central manager stores for each intended connection the list of the intermediate network elements calculated by the TE tool and in case of a backup connection activated for protecting the intended connection it also stores the list of the intermediate network elements of the backup connection. The centralized manager can be connected directly to the managed network elements or indirectly through channels carrying control data in the same physical network carrying user data or through a different physical network carrying only control data. In the new network architectures, based on the Automatically Switched Optical Network (ASON) defined in ITU-T G.8080/Y.1304 (11/2001), the backup connection is calculated by a control plane element (CPE), which controls one or more network elements, also defined Transport Plane Elements (TPE), for protecting the intended connections starting from the controlled network element (also defined source network element); in order to perform these functions, each CPE stores the list of identifiers of the intended connections starting from the controlled network element and stores for each intended connection the source and destination network elements, the list of the intermediate network elements (or the list of segments, identified by two network elements) of the intended connection calculated by the TE tool and in case of a backup connection activated for protecting the intended connection it also stores the list of the intermediate network elements of the backup connection. The CPEs are schematically indicated in FIG. 1.1-1.5 with CPE1, CPE2, CPE3, CPE4, CPE5, CPE6, CPE7, CPE8, CPE9 and CPE10; they are interconnected with each other and communicate according to a signaling protocol, in order to provide a fast detection of a failure, a fast and efficient configuration of new connections within the Transport Plane, modify the connections previously set up and perform a faster restoration function providing backup connections for protecting the intended connections. Various signalling protocols can fit the ASON architecture, like the Resource Reservation Protocol (RSVP) defined in RFC2205, RFC2209 and RFC2750, the Resource Reservation Protocol—Traffic Engineering (RSVP-TE) defined in RFC3209 and ITU-T G.7713.2, the Label Distribution Protocol (LDP) defined in RFC3036, the Constraint Based—Label Distribution Protocol (CR-LDP) defined in ITU-T G.7713.3 and RFC3472), the Private Network to Network Interface (PNNI) defined in ITU-T G.7713.1.
Referring to RSVP protocol, the base specification was designed to allow network elements (routers) to decide in advance, that is before the provisioning of the connection, if the network can meet the requirements of a Quality of Service (QoS) defined for the connection. The configuration of a new intended or backup connection is performed by transmitting and receiving a Path message, in case of a successful configuration of the connection, a Resv message in the reverse direction of the Path message or receiving a Path_err message in case of an unsuccessful configuration (for example for lack of network resources). Reversion is performed in a similar way as a new intended connection, using Path and Reservation (Resv) messages, but in a ‘make-before-break’ manner, that is the intended connection is setup before the backup connection is torn down. A number of extensions were added to support provisioning and maintenance of explicitly routed connections (defined LSP=label switched paths). Finally, RSVP-TE allows the aggregation of connections, defined LSP tunnels, which share a common route and a common pool of shared network resources, reducing the amount of information carried in the network. Moreover, when a failure is detected on a segment, it must be notified as fast as possible to all the source CPEs controlling the source network element of the intended connections crossing the failed segment, in order to route the traffic from the intended to a backup connection. A Notify message is defined for reporting of failures and it is described by Internet draft draft-ieff-mpls-generalized-rsvp-te-09.txt (September 2002), issued by IETF and updated periodically; this message includes the address of the CPE controlling the network element which has detected the failure.
In traffic engineered network the concept of dynamic sharing of network resources applies: a network resource (a segment or part of the bandwidth of the segment) can be assigned to more that one backup connection, while it must be assigned to one intended connection. For example, after rerouting of user traffic from a first intended to a first backup connection, a second backup connection can use available segments of the first intended connection (that is segments not anymore used by the first intended connection and not affected by a failure) for protecting a second intended connection affected by a failure. This mechanism allows a better usage of network resources, but the concurrent usage of the same resources by different connections can create blocking situations, also defined as “deadlock”. The deadlock is more probable in an ASON network, because of the parallelism of the distributed managers, that is of the CPEs, which can require to use the same resources (segments) at nearly the same time, for example for restoration purposes.
FIGS. 1.1, 1.2, 1.3, 1.4 and 1.5 show an example of the steps required for having a deadlock involving two intended connections; the intended connections (c1, c2) are indicated with a continuous line, the backup (b, b2, b1) with a broken line. Referring to FIG. 1.1, the first intended connection (cl) crosses network elements 1, 8 and 10, the second (c2) crosses 2, 3, 4, 6 and 9. At time t1 (FIG. 1.2) a failure F1 occurs on segment 8-10 of the first intended connection and a first backup connection (b) is provided (pre-calculated or calculated run-time) for protecting the first intended connection, crossing network elements 1, 4, 7, 9 and 10. At time t2 (FIG. 1.3) a failure F2 occurs on segment 4-6 of the second intended connection and a second backup connection (b2) is provided for protecting the second intended connection, crossing network elements 2, 1, 8 and 9: the second backup connection is using segment 1-8 of the first intended connection, which is available because the first intended connection is rerouted over the first backup connection. At time t3 (FIG. 1.4) a failure F3 occurs on segment 4-7 of the first backup connection and a third backup connection (b1) is provided (usually calculated run-time) for protecting the first intended connection, crossing network elements 1, 2, 3, 5, 7, 9 and 10: the third backup connection is using segment 2-3 of the second intended connection, which is available because the second intended connection is rerouted over the second backup connection. FIG. 1.5 shows the deadlock of the first and second intended connections: when all failures clear, neither b1 nor b2 can revert to c1 and c2 respectively, because one segment of c1 and c2 is not available. The figures show schematically the network resources interconnecting the network elements. For example, segment 1-2 carries two backup connections (b1 and b2); this is possible using one physical medium (an optical fibre, a coaxial cable, a radio link) carrying the two backup connections on different time slots (or on different wavelenghts) or alternatively it is possible using two different physical medium. In this example segment 1-2 must provide enough network resources for carrying b1 and b2 between network element 1 and 2 and b2 must use on segment 1-8 the same network resource (physical medium and bandwidth) used by c1.
FIG. 1.5 shows the deadlock involving two connections, but in a telecommunication network carrying many connections the deadlock can involve more than two connections; for example, FIG. 2 shows the deadlock involving four connections, wherein each backup connection is using a segment of a subsequent intended connection. In this scenario the reversion from the backup to the intended connection is not possible, although any failure is present in the network.
Nowadays the deadlock is avoided, that is the deadlock situation is not reached but it is prevented according to two solutions. In the first solution partial sharing of network resources is performed: a group of segments is assigned in advance for providing backup connections and these segments are used for protecting different intended connections. The deadlock is avoided defining a rule for assigning the shared segments, for example defining a different priority for each intended connection within the network or using a first come-first serve rule. Referring to priority rule, a first example is when two different intended connections require to use the same segments for protection for a failure on a segment of the corresponding intended connection: these segments are assigned to the intended connection having the highest priority (this is also indicated with ‘contention’). In this first solution usage of network resources is not optimized (because only segments of the group are shared) and consequently more resources are required for protection of intended connections; moreover, it requires the definition of a rule, which can be complex in case of a network including many connections. In the second solution complete sharing of network resources is performed; in fact, as explained above, after routing of traffic from an intended to a backup connection, available segments of the intended connection can be used for backup connections, that is also segments of intended connections can be dynamically shared. In this second solution deadlock is avoided because an existing connection which was first successfully established, is intentionally torn down (this is also indicated with ‘pre-emption’); referring to FIG. 1.4, in case of clearing of failure F1, if c1 has a priority higher than c2, b2 (protecting c2) will be released. In order to avoid loss of traffic, a further backup connection is calculated for protecting c2 (further segments are required in the network), afterwards b2 is released and consequently the traffic can be reverted from the backup b1 to the intended connection c1. This second solution has the same disadvantages of the first solution, that is to require the definition of a rule and to require more network resources; moreover, the second solution is possible in a network controlled by a central manager, because the manager stores the list of all connections (and the priorities) of the controlled domain, but is not possible in a network controlled by a distributed manager, because each CPE stores only the list of the connections (and the priorities) starting from the controlled network element.